//1.摩尔斯投票法 | 数组中出现次数超过一半的数字 | 众数


//例如我们有这样一组数据：3、4、1、1、2、5、5、5、6、7

//我们用投票的思想，众数的票数一定多余其他数字的票数，对吧？

//1.但是我们不知道哪个是众数，我们直接从第一个arr[0]开始拿，

//2.把 3 当作众数，初始票数为 a=1；

//3.取第下一个arr[1]，发现是 4，与3不一样，则 a--，此时a=0；

//4.因为 3 和 4 的票数相互抵消了，所以我们应该以再下一个arr[2]就是第三个数字 1 当众数； 

//5.取第下一个arr[i+1]，发现是 1，与 arr[2] 一样，那我们就a++；

//6.取下一个数字重复操作。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int a=1,x=nums[0];//x为临时众数；
        for(int i=1;i<nums.size();i++){
            if(x==nums[i]) a++; //一样，票数加一； 
            else a--;//不一样票数减一；
            if(a==0) { //没有票了，我们取下一个当众数；
                x=nums[i+1];
                a=1;
                i++; //因为我们已经取了下一个，所以要把i指向 现在众数，这样下一次循环才会与 现在的众数 的下一个进行比较；
            }
        }
        return x;//返回真正的众数。
    }
};
